package com.dragon.datastructure.search;

/**
 * 二分查找
 *
 * @author dragon
 * @since 2019/12/26
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        int i = binarySearch(array, 0, array.length - 1, 1);
        System.out.println(i);
    }

    /**
     * 根据二分查找查询findValue是否在array中，如果在则返回该索引值，如果不在，则返回 -1
     *
     * @param array     查询的数组
     * @param left      左边索引
     * @param right     右边索引
     * @param findValue 要找的值
     * @return 返回的索引，如果找不到，则返回 -1
     */
    public static int binarySearch(int[] array, int left, int right, int findValue) {
        System.out.println("hello!");
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (findValue > array[mid]) {
            return binarySearch(array, mid + 1, right, findValue);
        } else if (findValue < array[mid]) {
            return binarySearch(array, left, mid - 1, findValue);
        } else {
            return mid;
        }
    }
}
